pub struct PriorityQueue<T, F: Fn(&T, &T)-> bool> {
    cmp: F,
    pq: Vec<T>,
}

impl<T, F> PriorityQueue<T, F> where F: Fn(&T, &T) -> bool {
    pub fn new(cmp: F) -> Self {
        let pq = Vec::new();
        Self {
            cmp,
            pq,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.pq.is_empty()
    }

    pub fn len(&self) -> usize {
        self.pq.len()
    }

    pub fn insert(&mut self, t: T) {
        self.pq.push(t);
        self.swim(self.pq.len())
    }

    pub fn append<I>(&mut self, s: I) where I: IntoIterator<Item = T> {
        for i in s {
            self.insert(i);
        }
    }

    pub fn del_max(&mut self) -> Option<T> {
        if !self.is_empty() {
            self.exch(1, self.pq.len());
            let max = self.pq.pop();
            self.sink(1);
            return max;
        }
        None
    }

    pub fn log_debug(&self) where T: std::fmt::Debug {
        let mut idx = 1;
        let mut r = 1;
        for (i, val) in self.pq.iter().enumerate() {
            if i >= r {
                println!();
                idx *= 2;
                r += idx;
            }
            print!("{:?} ", val);
        }
        println!();
    }

    fn get(&self, i: usize) -> Option<&T> {
        if i > self.pq.len() || i <= 0 {
            None
        } else {
            Some(&self.pq[i - 1])
        }
    }

    fn exch(&mut self, i: usize, j: usize) {
        self.pq.swap(i - 1, j - 1)
    }

    fn swim(&mut self, mut k: usize) {
        while k > 1 && (self.cmp)(self.get(k >> 1).unwrap(), self.get(k).unwrap()) {
            self.exch(k >> 1, k);
            k >>= 1;
        }
    }

    fn sink(&mut self, mut k: usize) {
        while 2 * k <= self.pq.len() {
            let mut j = 2 * k;
            if j < self.pq.len() && (self.cmp)(self.get(j).unwrap(), self.get(j + 1).unwrap()) {
                j += 1 
            }
            if !(self.cmp)(self.get(k).unwrap(), self.get(j).unwrap()) { 
                break 
            }
            self.exch(k, j);
            k = j
        }
    }
}